package com.rn.gypsophila.dsalg.arrary;

import java.util.*;

/**
 * 题目：
 * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
 * 请你合并所有重叠的区间，并返一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
 * 链接：<a href="https://leetcode.cn/leetbook/read/array-and-string/c5tv3/">...</a>
 *
 * @author 然诺
 * @since 2023/2/25
 */
public class MergeInterval {

    public static int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length <= 1) {
            return intervals;
        }
        // 先排序
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
        // 合并区间
        List<int[]> newIntervals = new ArrayList<>();
        int[] temp = intervals[0];
        for (int i = 1; i < intervals.length; i++) {
            if (temp[1] < intervals[i][0]) {
                newIntervals.add(temp);
                temp = intervals[i];
            } else {
                temp[1] = Math.max(temp[1], intervals[i][1]);
            }
        }
        newIntervals.add(temp);
        return newIntervals.toArray(new int[newIntervals.size()][2]);
    }

    public static void main(String[] args) {
        System.out.println(Arrays.deepToString(merge(new int[][]{{1, 3}, {2, 6}, {8, 10}, {15, 18}})));
        System.out.println(Arrays.deepToString(merge(new int[][]{{1, 4}, {4, 5}})));
        System.out.println(Arrays.deepToString(merge(new int[][]{{1, 3}})));
        System.out.println(Arrays.deepToString(merge(new int[][]{{}})));
    }
}
